package main

import (
	"fmt"
	"time"
)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val > l2.Val {
		return mergeTwoLists(l2, l1)
	}
	p := l1
	t := l2
	for nil != p.Next {
		if l2.Val < p.Next.Val {
			// 把节点出入链中
			l2 = l2.Next
			t.Next = p.Next
			p.Next = t

			//判断l2是否到结尾
			if nil == l2 {
				break
			}
			t = l2
		}
		p = p.Next
	}
	// 如果l1到结尾，但是l2还有内容
	if nil != l2 {
		p.Next = l2
	}

	return l1
}

// func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 	if l1 == nil {
// 		return l2
// 	}
// 	if l2 == nil {
// 		return l1
// 	}
// 	if l1.Val > l2.Val {
// 		return mergeTwoLists(l2, l1)
// 	}

// 	p := l1
// 	t := p.Next
// 	for nil != p.Next {
// 		// fmt.Println(l2.Val)
// 		if l2.Val < p.Next.Val {
// 			t = p.Next
// 			p.Next = l2
// 			if l2.Next == nil {
// 				p.Next.Next = t
// 				break
// 			}
// 			l2 = l2.Next
// 			p.Next.Next = t
// 		}
// 		p = p.Next
// 		t = p
// 	}
// 	p.Next = l2
// 	return l1

// }

// 递归调用示例
// /**
//  * Definition for singly-linked list.
//  * public class ListNode {
//  *     int val;
//  *     ListNode next;
//  *     ListNode(int x) { val = x; }
//  * }
//  */
//  class Solution {
//     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//         if(l1 == null) {
//             return l2;
//         }
//         if(l2 == null) {
//             return l1;
//         }

//         if(l1.val < l2.val) {
//             l1.next = mergeTwoLists(l1.next, l2);
//             return l1;
//         } else {
//             l2.next = mergeTwoLists(l1, l2.next);
//             return l2;
//         }
//     }
// }

func main() {
	start := time.Now()
	node := ListNode{1, nil}
	node1 := ListNode{2, nil}
	node2 := ListNode{4, nil}
	link1 := &node
	node.Next = &node1
	node1.Next = &node2
	nodeb := ListNode{1, nil}
	nodeb1 := ListNode{3, nil}
	nodeb2 := ListNode{4, nil}
	link2 := &nodeb
	nodeb.Next = &nodeb1
	nodeb1.Next = &nodeb2
	dec := mergeTwoLists(link1, link2)
	cost := time.Since(start)
	for nil != dec {
		fmt.Println(dec.Val)
		dec = dec.Next
	}
	fmt.Println(cost)
}
